package com.ctrip.demo.stack;

import com.ctrip.demo.java8.A;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolandNotation {

    public static void main(String[] args) {
        String expression = "1+((2+3)*5)-6";
        List<String> toInfixExpressionList = toInfixExpressionList(expression);
        System.out.println(toInfixExpressionList);
        // 中缀表达式转后缀表达式
        List<String> suffixExpressionList = parseSuffixExpressionList(toInfixExpressionList);
        System.out.println(suffixExpressionList);

        System.out.println("计算结果：" + calculate(suffixExpressionList));
    }

    public static int calculate(List<String> suffixExpressionList) {
        Stack<String> stack = new Stack<>();
        for (String item : suffixExpressionList) {
            if (item.matches("\\d+")) {
                stack.push(item);
            } else {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num2 - num1;
                } else if (item.equals("*")) {
                    res = num2 * num1;
                } else if (item.equals("/")) {
                    res = num2 / num1;
                }
                // 将结果压入栈中
                stack.push(res + "");
            }
        }
        return Integer.parseInt(stack.pop());
    }

    /**
     * 中缀表达式转后缀表达式
     * @param toInfixExpressionList 中缀表达式集合
     * @return
     */
    public static List<String> parseSuffixExpressionList(List<String> toInfixExpressionList) {
        // 存储中间结果
        List<String> res = new ArrayList<>();
        // 符号栈
        Stack<String> stack = new Stack<>();

        for (String item : toInfixExpressionList) {
            // 匹配数字
            if (item.matches("\\d+")) {
                res.add(item);
            } else if (item.equals("(")) {
                stack.push(item);
            } else if (item.equals(")")) {
                // 如果是有括号，则依次弹出stack栈顶的运算符，并且压入到res，直到遇到左括号，此时将这一对括号丢弃
                while (!stack.peek().equals("(")) {
                    res.add(stack.pop());
                }
                // 将stack中括号弹出，消除括号
                stack.pop();
            } else {
                // 运算符号
                // 当item优先级小于等于stack栈顶运算符号，将stack栈顶的运算符弹出并加入到res中，
                while (stack.size() != 0 && Operation.getValue(stack.peek()) >= Operation.getValue(item)) {
                    res.add(stack.pop());
                }
                // 将当前的运算符push到栈中
                stack.push(item);
            }
        }

        // 最后将stack栈中的数据依次放入到res中
        while (!stack.isEmpty()) {
            res.add(stack.pop());
        }
        return res;
    }

    /**
     * 中缀表达式转list
     * @param express 表达式
     * @return
     */
    public static List<String> toInfixExpressionList(String express) {
        List<String> ls = new ArrayList<>();
        // 拼接多位数
        String s = "";
        int idx = 0;
        do {
            // 非数字
            if (express.charAt(idx) < 48 || express.charAt(idx) > 57) {
                ls.add(""+express.charAt(idx ++));
            } else {
                s = "";
                while (idx < express.length() && express.charAt(idx) >= 48 && express.charAt(idx) <= 57) {
                    s += express.charAt(idx ++);
                }
                ls.add(s);
            }

        } while (idx < express.length());

        return ls;

    }

}
class Operation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    public static int getValue(String operation) {
        int res = 0;
        switch (operation) {
            case "+":
                res = ADD;
                break;
            case "-":
                res = SUB;
                break;
            case "*":
                res = MUL;
                break;
            case "/":
                res = DIV;
                break;
            default:
                System.out.println("非法运算符");
                break;
        }
        return res;
    }
}
